/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* next;
    Node* random;
    
    Node(int _val) {
        val = _val;
        next = NULL;
        random = NULL;
    }
};
*/

class Solution {
public:
    Node* copyRandomList(Node* head) {
        map<Node*,Node*> mp;
        Node* cur = head;
        Node* copyhead = nullptr,*copytail = nullptr;
        while(cur)
        {
            if(copytail==nullptr){
                copyhead = copytail = new Node(cur->val);
            }else{
                copytail->next = new Node(cur->val);
                copytail = copytail->next;
            }
            mp[cur]=copytail;
            cur=cur->next;
        }
        cur = head;
        Node* copycur = copyhead;
        while(copycur)
        {
            copycur->random = mp[cur->random];
            copycur = copycur->next;
            cur = cur->next;
        }
        return copyhead;
    }
};